Batch 3 - Class 251 - Induction
(Zoom)
Pre-Class Exercise
Attendance Kabir, Mihir, Advay, Vansh, Raghav, Angad, Aarkin, Ayush, Aneesh, Shikhar, Arnav, Kushagra, Anshi, Rohan, Rhea, Rehaan, Anishka, Aashvi
Class Notes: (Repeat from Class 141, 143)
Review of Computational Thinking - Key elements
Abstraction: There is a graph, with nodes and edges. Abstraction involves focusing on what is important and ignoring the rest - for example, we have not shown how much each tourist attraction cost for entry.
Generalization: Both problems are similar problems - ask students in what respect. Both problems involved going from one point to all other points and coming back to the original problem.
Algorithm: The method to solve the problem. How did you go about traversing the graph? For this kind of the problem, depth first is an intuitive route - you go down a path as far as you can and you backtrack if its the wrong path and try another one.
Pattern Matching: It seems that we can solve any "route finding" problem by drawing a graph for that - this is pattern matching.
Relate to the above in context of the knight's tour, tour guide and circular numbers discussed earlier and search (directory, guess who, 20 questions) discussed last week.
We also learned that searching through a sorted list is much easier than jumbled lists, and mechanisms of sorting such as bubble sort, merge sort.
Induction
- (MC - 9 - 1) One square was cut from a 16x16 sqaure grid. Prove that the figure obtained can be dissected into trominos (3 squares in corner shape).
Instructor Notes: Let students think and about the problem, and come up with some answers. Note that simple divisibility by 3 doesn't suffice. After a bit, ask them to solve the problem for a 2x2 square. Once that is done, as them to do it for 4x4. They might do it by taking three possible cases. Guide them towards thinking about a 4x4 square as composition of 2x2 squares. Then 8x8 - by now the pattern must get intuitive.
- What can we say about any square?
- Careful: We have just said something about powers of 2, not an arbitrary square!
- Visualization
- How can we generalize the statement?
- Take the dominos analogy - to illustrate that the first domino requires a push (i.e. base case), and then every domino will fall if the previous one falls (i.e. induction step)
Introduce notion of variable. And then formalize the proof of this problem. (If 2^nx2^n square missing a square can be cut into trominos, then so can a 2^(n+1)x2^(n+1) square missing a square)
Introduce the terminology - Induction, Induction Hypothesis, Base, and Induction Step
- (Decade - 6 - 2.2) Another simple example: Upon being defeated and forced to abandon his castle forever, an evil magician casts a spell: if it rains one day over the castle, then it will rain the next day too. It happens to rain there today. What can we say about the future?
- Answer: It will rain forever. Get kids to identify the hypothesis, base and induction steps
- (Decade - 6 - 3.1) Prove that sum of first n odd natural numbers is n^2
- Instructor Notes: Clarify that the above statement is the induction hypothesis
- What should be the basis? Is that provable?
- What should be the induction step? Can you prove that step?
- Steps in Induction proofs
- The Hypothesis
- Trick to forming a hypothesis - solve for smallest 4-5 cases - try to spot the pattern
- Basis Step
- Induction Step - Note that Induction step only assumes that the hypothesis holds upto "n", and not in general - that is what we are trying to prove.
- Caution - Wrong Proofs using Induction - let the kids spot the errors
- (Decade - 6 - Section 6 - 1) All natural numbers are even - Assume that any natural number up to n is even. We want to prove that n+1 is also even. Since n+1=n-1+2. What's wrong?
- We have not proven our base hypothesis. 1 is odd
- (Decade - 6 - Section 6 - 2) All dogs are the same color - Basis step: 1 dog is obviously of the same color. Take n+1 dogs. If all sets of n dogs are the same color, then take a dog A out and rest must be of same color. Now take a dog B out and rest must be of same color. In the dogs left in both cases, there is a dog C, which is common. And hence the two sets need to be of same color. Hence proved.
- We have assumed at least three dogs, so we must prove for 2 dogs, not just for one. Our induction step doesn't hold for 2 dogs.
- What has this got to do with Computational Thinking
- What is mathematical induction - a generalization? an abstraction? a method? a pattern?
- How do you take induction and apply it to computational problems?
Homework:
- (MC - 9 - 6) Into how many regions do n lines divide the plane, given that none of them are parallel, and not more than two intersect at a point.
- You will first have to form the hypothesis. Solve for a few cases (small values on n) to develop the hypothesis
- Now, the hypothesis using induction
References:
Mathematical Circles (Russian Experience), by Dmitri Fomin, Sergey Genkin, Ilia Itenberg
A Decade of the Berkeley Math Circle. The American Experience, Volume 1. Zvezdelina Stankova, Tom Rike